Question I

(a) What would be optimal data structures to store the graph for the above two algorithms ? (2 point)

Optimal data structure for Floyd-Warshall Algorithm - Two dimensional array - Adjacency matrix Dijkstra's Algorithm - Adjacency list and priority queue

(b) If the graph has |E| edges and |V| vertices, what would be corresponding time-complexities (O-notations) for the two algorithms to calculate the shortest path between all the vertices (assuming the use of the data structures as above)?

Floyd-Warshall Algorithm - O(n^3) Dijkstra's Algorithm - O(|E| + |V|log|V|)

Question II

(a) Execute the algorithm on the weighted directed graph as shown in Fig.1 and calculate the shortest distances between node 1 and all other nodes. (3 points) (b) Using back tracking, calculate the shortest path from node 1 to all other nodes. Indicate the data structures used and its corresponding entries at every iteration. (3 points)



In [ ]:

    
graphUsed = { 'V1' : [['V2', 6], ['V3', 2], ['V4', 16]],
				'V2' : [['V4', 5], ['V5', 4]],
				'V3' : [['V2', 7], ['V5', 3], ['V6', 8]],
				'V4' : [['V7', 3]],
				'V5' : [['V4', 4], ['V7', 10]],
				'V6' : [['V7', 1]],
				'V7' :  []}

distances = {}
previous = {}
vertexList = ['V1', 'V2', 'V3', 'V4', 'V5', 'V6', 'V7']

def Dijkstra(graphUsed, source):

	for key in graphUsed:
		distances[key] = 100000000
		previous[key] = 'none'

	min = distances[source] = 0
	smallestDisVertex = source
	indexEle = vertexList.index(source)

	i=0
	while vertexList:
		if min > distances[vertexList[i]]:
			min = distances[vertexList[i]]
			indexEle = i
		smallestDisVertex = vertexList.pop(indexEle)
		print("Smallest Distance Vertex is ", smallestDisVertex)
		for neighList in graphUsed[smallestDisVertex]:
			altDist = distances[smallestDisVertex] + neighList[1]
			if altDist < distances[neighList[0]]:
				distances[neighList[0]] = altDist
				previous[neighList[0]] = smallestDisVertex
				print(distances[neighList[0]], previous[neighList[0]])
	print(distances)
	print(previous)
	
def shortestPath(destination, previous):
	path = [destination]
	node = destination
	while previous[node] != 'none':
		node = previous[node]
		path.append(node)
		print("Creating a path", path)
	print(path)

Dijkstra(graphUsed, 'V1')
shortestPath('V7', previous)

(b) Using back tracking, calculate the shortest path from node 1 to all other nodes. Indicate the data structures used and its corresponding entries at every iteration. (3 points)



In [ ]:

Question III

Consider a set of 5 towns. The cost of construction of a road between towns i and j is a ij and is shown in the matrix M below. Find the minimum cost road network connecting the towns with each other. (4 points)



In [ ]: